package 力扣热题100;

import java.util.ArrayList;
import java.util.List;

public class LeetCode12 {
    List<String> list = new ArrayList<>();//用来放结果

    public List<String> generateParenthesis(int n) {
        if (n <= 0) {
            return list;
        }
        String ret = "";
        combination(ret, n, n);
        return list;
    }

    private void combination(String str, int left, int right) {
        if (left == 0 && right == 0) {
            list.add(str);
            return;
        }
        if (left == right) {//如果左边和右边的括号相等那就只能放左括号
            combination(str + "(", left - 1, right);
        } else if (left < right) {//如果左边比右边多那么左右都可以放
            if (left > 0){//但要注意放左括号的前提
                combination(str + '(', left - 1, right);
            }
            combination(str + ')', left, right - 1);//放右括号
        }
    }

    public static void main(String[] args) {
        LeetCode12 leetCode12=new LeetCode12();
        leetCode12.generateParenthesis(3);
    }
}
